package org.labuladong.动态规划算法.一维DP;

import java.util.Arrays;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-17:24
 * @Description:
 *
 * 标签：动态规划，⼀维动态规划，⼆分搜索
 * 给你⼀个⼆维整数数组 envelopes，其中 envelopes[i] = [wi, hi]，表示第 i 个信封的宽度和⾼度。
 * 当另⼀个信封的宽度和⾼度都⽐这个信封⼤的时候，这个信封就可以放进另⼀个信封⾥，如同俄罗斯套娃⼀样。
 * 请计算 最多能有多少个信封能组成⼀组“俄罗斯套娃”信封（即可以把⼀个信封放到另⼀个信封⾥⾯）。
 * 注意：不允许旋转信封。
 * 示例 1：
 * 输⼊：envelopes = [[5,4],[6,4],[6,7],[2,3]]
 * 输出：3
 * 解释：最多信封的个数为 3, 组合为：[2,3] => [5,4] => [6,7]。
 *
 * 本题相当于在⼆维平⾯⾥⾯求最⻓递增⼦序列
 * @version: 1.0
 */
public class LC_354_俄罗斯套娃信封问题 {

	public static int maxEnvelopes(int[][] envelopes)
	{
		int n = envelopes.length;
		if (n == 0) return 0;

		// ⾃然排序，先按宽度升序，宽度相同再按⾼度降序
		Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

		// ⾃然排序，先按宽度升序，宽度相同再按⾼度降序
		int[] f = new int[n];
		int res = 1;
		f[0] = 1;
		for (int i = 1; i < n; i++)
		{
			int max = 0;
			for (int j = 0; j < i; j++)
			{
				if (envelopes[j][1] < envelopes[i][1])
				{
					max = Math.max(max, f[j]);
				}
			}
			f[i] = max + 1;
		}

		for (int i = 0; i < n; i++)
		{
			res = Math.max(res, f[i]);
		}
		return res;
	}

	public static void main(String[] args) {

		int[][] envelopes = {{5,4},{6,4},{6,7},{2,3}};
		int res = maxEnvelopes(envelopes);
		System.out.println(res);
	}
}
